package com.Offer;

import java.util.Scanner;


/*
    面试题4：二维数组的查找
    面试题:在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列 都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
    测试用例：
    1 2 8 9
    2 4 9 12
    4 7 10 13
    6 8 11 15
 */
public class demo4 {

    static int m = 4;
    static int n = 4;
    static int[][] arr = new int[m][n];

    public static void main(String[] args) {
        long start = System.currentTimeMillis();
        Scanner sc = new Scanner(System.in);
        for(int i = 0;i<m;i++){
            for(int j = 0;j<n;j++){
                arr[i][j] = sc.nextInt();
            }
        }
        //System.out.println(findNum(5));
        System.out.println(find2(arr,7));
        long end = System.currentTimeMillis();
        System.out.println("程序运行时间： "+(end-start)+"ms");
    }

    public static boolean findNum(int x){
        if(x > arr[m-1][n-1] || x < arr[0][0]){
            return false;
        }
        int i = 0;
        int j = n-1;
        while(i<m && j>=0){
            if(x == arr[i][j]){
                return true;
            }else if(x > arr[i][j]){
                i++;
            }else{
                j--;
            }
        }
        return false;
    }

    //二分法查找
    public static boolean find2(int[][] array, int target) {
        if (array == null || array.length == 0) {
            return false;
        }int left = 0;
        int right = array.length * array[0].length - 1;
        int col = array[0].length;
        while (left <= right) {
            int mid = (left + right) / 2;
            int value = array[mid / col][mid % col];
            if (value == target) {
                return true;
            } else if (value < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return false;
    }

}
